1. Field of the Invention
The present invention relates to a communication path control apparatus and a method therefor, and, more particularly, to a packet transfer path control apparatus and a method therefor for selecting packet transfer paths minimizing the possibility of packets arriving at a destination in the order different from the order in which they were transmitted.
2. Description of the Background Art
In packet communication in which data are transmitted in the form of packets, a multiple-path transmission system is generally adopted. The multiple-path transmission environment involves a problem in that, if a lot of packets to deal with are bunched to a specific node on a packet transmission network, they may arrive at destinations with more delay than the packets routed through other nodes.
Therefore, routers, or nodes, constituting a packet transfer network are adapted, when connected to plural adjacent routers, to transmit received packets to the adjacent routers in such a way that the traffic load of packets to be transmitted is equally shared between the adjacent routers. For example, in the simplest method, a router assigns packets equally in number between all its adjacent routers. As an alternative solution, Srikanth Kandula et al., “Dynamic Load. Balancing Without Packet Reordering” ACM SIGCOMM Computer Communication Review, Vol. 37, No. 2, April 2007 discloses a method in which the first branch for packets to be transmitted on a packet transfer network controls the order of transmitting packets so that individual routs equally share the load therebetween.
However, there may be a case where packets routed on plural paths will be congested at another node on the network. In such a case, if routers equally distribute packets between all the adjacent routers, a number of packets may concentrate on a router located at a junction of the plural routs near the destination thereof. Therefore, there is a possibility that the router at the junction delays in processing the packets thus concentrated, thus causing a difficulty that the packets transmitted would not reach the destination in the order different from the order in which they were transmitted.
For example, a case will be described where data are transmitted from a source host to a destination host over a packet transfer network, which includes seven routers, or nodes, R1 to R7, which are adapted to evenly distribute received packets between routers adjacent thereto to which they will be transferred. For example, the source host transmits 60 packets meant for the destination host to the first router R1, which in turn receives the 60 packets and evenly distributes them between the routers R2 and R3 that are adjacent to the router R1 towards the destination thereof. In turn, each of the routers R2 and R3 receives 30 packets. On one hand, the router R2 evenly distributes the 30 packets received between the routers R4 and R5 that are adjacent to the router R2 towards the destination to transmit 15 packet to each of the routers R4 and R5. On the other hand, the router R3 receives 30 packets and evenly distributes the latter between the routers R5 and R6 adjacent to the router R3 towards the destination to transmit 15 packets to each of the routers R5 and R6. Each of the routers R4 and R5 receives 15 packets from the router R2 while each of the routers R5 and R6 receives 15 packets from the router R3. In this example, as may be noted, the router R5 is interconnected to both of the routers R2 and R3, so that the router R5 is located at the junction of the routes passing through the routers R1 and R2 and through the routers R1 and R3. The router R5 thus receives 30 packets in total from the routers R2 and R3 whereas the routers R4 and R6 receive 15 packets each from the routers R2 and R3, respectively.
In this way, the packets transmitted over the routes through the router R5, i.e. the routes passing through the routers R1, R2, R5 and R7, and through the routers R1, R3, R5 and R7, concentrate on the router R5, so that the router R5 may be caused to delay the processing of those packets. Therefore, there is a higher possibility that the packets transmitted through the router R5 arrive at the destination host in delay against the other packets transmitted without passing the router R5, i.e. on the routes passing the routers R1, R2, R4 and R7, and through the routers R1, R3, R6 and R7. That may cause the packets to be received in the order different from the order in which they are transmitted from the source host, thus requiring the packets received to be reordered.